/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：CountingSort.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-21
Function List ：
Description   ：Counting Sort
******************************************************/

#include "CountingSort.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

void CountingSort(ElementType A[], int N) {
    int i;
    int Count;
    int Range;
    int MinValue;
    int MaxValue;
    int *Tmp;

    /* Find min and max values */
    MinValue = A[0];
    MaxValue = A[0];
    for (i = 0; i < N; ++i) {
        if (A[i] < MinValue) {
            MinValue = A[i];
        } else if (A[i] > MaxValue) {
            MaxValue = A[i];
        }
    }

    /* Allocate a array and initialize to 0 */
    Range = MaxValue - MinValue + 1;
    Tmp = (int *)calloc(Range, sizeof(int));
    if (Tmp == NULL) {
        FatalError("Out of space!!!");
    }

    /* Count every elements */
    for (i = 0; i < N; ++i) {
        ++Tmp[A[i] - MinValue];
    }

    /* Recycling elements */
    Count = 0;
    for (i = 0; i < Range; ++i) {
        while (Tmp[i]--) {
            A[Count] = i + MinValue;
            ++Count;
        }
    }

    /* Free allocated space */
    free(Tmp);
}

// EOF

